#include "btree.h"
#include <stdio.h>

/**
 * 辅助函数：递归实现先序遍历
 * @param node 当前节点
 * @param callback 回调函数
 */
static void pre_order_helper(btreenode* node, void (*callback)(int)) {
    if (node == NULL) {
        return;
    }
    callback(node->data);           // 访问当前节点
    pre_order_helper(node->left, callback);  // 递归遍历左子树
    pre_order_helper(node->right, callback); // 递归遍历右子树
}

/**
 * 二叉树的先序遍历
 * @param bt 二叉树指针
 * @param callback 回调函数
 */
void pre_order_visit(btree* bt, void (*callback)(int)) {
    if (bt == NULL || bt->root == NULL) {
        return;
    }
    pre_order_helper(bt->root, callback);
}

/**
 * 辅助函数：递归实现中序遍历
 * @param node 当前节点
 * @param callback 回调函数
 */
static void in_order_helper(btreenode* node, void (*callback)(int)) {
    if (node == NULL) {
        return;
    }
    in_order_helper(node->left, callback);  // 递归遍历左子树
    callback(node->data);                  // 访问当前节点
    in_order_helper(node->right, callback); // 递归遍历右子树
}

/**
 * 二叉树的中序遍历
 * @param bt 二叉树指针
 * @param callback 回调函数
 */
void in_order_visit(btree* bt, void (*callback)(int)) {
    if (bt == NULL || bt->root == NULL) {
        return;
    }
    in_order_helper(bt->root, callback);
}

/**
 * 辅助函数：递归实现后序遍历
 * @param node 当前节点
 * @param callback 回调函数
 */
static void post_order_helper(btreenode* node, void (*callback)(int)) {
    if (node == NULL) {
        return;
    }
    post_order_helper(node->left, callback);  // 递归遍历左子树
    post_order_helper(node->right, callback); // 递归遍历右子树
    callback(node->data);                    // 访问当前节点
}

/**
 * 二叉树的后序遍历
 * @param bt 二叉树指针
 * @param callback 回调函数
 */
void post_order_visit(btree* bt, void (*callback)(int)) {
    if (bt == NULL || bt->root == NULL) {
        return;
    }
    post_order_helper(bt->root, callback);
}


/**
 * 二叉树的层序遍历
 * @param bt 二叉树指针
 * @param callback 回调函数
 */
void level_visit(btree* bt, void (*callback)(int)) {
    if (bt == NULL || bt->root == NULL) {
        return;
    }

    // 创建一个队列用于层序遍历
    typedef struct queue_node {
        btreenode* tree_node;
        struct queue_node* next;
    } queue_node;

    typedef struct queue {
        queue_node* front;
        queue_node* rear;
    } queue;

    // 初始化队列
    queue* q = (queue*)malloc(sizeof(queue));
    q->front = q->rear = NULL;

    // 将根节点入队
    queue_node* new_node = (queue_node*)malloc(sizeof(queue_node));
    new_node->tree_node = bt->root;
    new_node->next = NULL;
    q->front = q->rear = new_node;

    // 层序遍历
    while (q->front != NULL) {
        // 出队
        queue_node* temp = q->front;
        btreenode* current = temp->tree_node;
        q->front = q->front->next;

        // 访问当前节点
        callback(current->data);

        // 将左子节点入队
        if (current->left != NULL) {
            queue_node* left_node = (queue_node*)malloc(sizeof(queue_node));
            left_node->tree_node = current->left;
            left_node->next = NULL;
            if (q->front == NULL) {
                q->front = q->rear = left_node;
            } else {
                q->rear->next = left_node;
                q->rear = left_node;
            }
        }

        // 将右子节点入队
        if (current->right != NULL) {
            queue_node* right_node = (queue_node*)malloc(sizeof(queue_node));
            right_node->tree_node = current->right;
            right_node->next = NULL;
            if (q->front == NULL) {
                q->front = q->rear = right_node;
            } else {
                q->rear->next = right_node;
                q->rear = right_node;
            }
        }

        // 释放出队节点
        free(temp);
    }

    // 释放队列
    free(q);
}